package com.xq.algorithm.binarytree;

/**
 * @author jltxseo
 *         Created by junlintianxia on 2017/07/22.
 *         判断二叉搜索树的后序遍历序列
 *         BST的后序遍历的合法序列满足：

对于一个序列S，最后一个元素是根元素，假设为x； 如果去掉根元素剩下的序列为T，那么T满足：前一段（左子树）小于x，后一段（右子树）大于x，且这两段（子树）也是合法的后序序列。
 */

public class BSTAlgorithm {

    public boolean verifySquenceOfBST(int[] sequence){
        if(sequence == null || sequence.length == 0) return false;
        return IsTreeOfBST(sequence,0,sequence.length - 1);
    }

    public boolean IsTreeOfBST(int[] sequence,int start, int end){ //子数组为空
        if(end <= start) return true;

        int i=0;
        for (; i < end; i++){ //找到左右子树分割点
            if (sequence[i] > sequence[end])break;
        }

        for (int j=i; j < end; j++){
            if(sequence[j] < sequence[end])return false;
        }

        return IsTreeOfBST(sequence,0,i - 1) && IsTreeOfBST(sequence,i,end -1);
    }
}
